package BFS解决FloodFill算法;

import java.util.*;

public class 最小基因变化 {

    int [] dx = {0, 0, 1, -1};
    int [] dy = {1,-1, 0, 0};

    char [] change = {'A', 'C', 'G', 'T'};

    public int minMutation(String start,String end, String[] bank) {
       Set<String> vis = new HashSet<>();
       Set<String> hash = new HashSet<>();

        for (String s : bank)
           hash.add(s);

        if(start.equals(end)) return 0;
        if(!hash.contains(end)) return -1;

        Queue<String> q = new LinkedList<>();
        q.add(start);
        vis.add(start);

        int step = 0;
        while (!q.isEmpty()) {
            step++;
            int sz = q.size();
            while (sz-- != 0) {
                String tmp = q.poll();
                for (int j = 0; j < 8; j++) {
                    char [] temp = tmp.toCharArray();
                    for (int k = 0; k < 4; k++)
                    {

                        temp[j] = change[k];
                        String s = new String(temp);
                        if (hash.contains(s) && !vis.contains(s)) {
                            if (s.equals(end))
                                return step;
                            else {
                                q.add(s);
                                vis.add(s);
                            }
                        }

                    }

                }

            }

        }
        return -1;
    }
}
